package cn.lishiyuan.algorithm.tree;

import java.util.Objects;

/**
 * 二叉搜索树实现
 */
public class BinarySearchTree<T extends Comparable<T>> implements LeeTree<T>{

    private Node<T> root;
    private int size = 0;

    public static class Node<T>{
        private T data;
        private Node<T> left;
        private Node<T> right;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(T element) {
        if (element == null){
            return false;
        }
        Node<T> node = findNode(element);

        return Objects.nonNull(node);
    }

    @Override
    public T find(T element) {
        if (element == null){
            return null;
        }
        Node<T> node = findNode(element);
        return node.data;
    }

    @Override
    public void add(T element) {
        if (element == null){
            throw new NullPointerException();
        }
        Node<T> node = findNode(element);
        // 不支持重复节点
        if (Objects.isNull(node)){
            node = newNode(element);

            if (Objects.isNull(root)){
                root = node;
                size++;
            }else {
                Node<T> pnode = root;
                // 查找合适的位置
                while (true){
                    // 比当前节点小，向左树查找
                    if (node.data.compareTo(pnode.data) < 0){
                        if (pnode.left == null){
                            pnode.left = node;
                            size++;
                            break;
                        }else {
                            pnode = pnode.left;
                        }
                    }else {
                        if (pnode.right == null){
                            pnode.right = node;
                            size++;
                            break;
                        }else {
                            pnode = pnode.right;
                        }
                    }
                }
            }
        }
    }

    /**
     * 第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。
     * 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
     * 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。
     * 然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。
     * @param element
     * @return
     */
    @Override
    public T remove(T element) {
        if (element == null){
            throw new NullPointerException();
        }

        // 查找元素
        Node<T> node = root;
        Node<T> parent = null;
        while (node!=null) {
            if (node.data.compareTo(element)==0) {
                break;
            }else if (node.data.compareTo(element) > 0){
                // 向右
                parent =node;
                node= node.right;
            }else {
                // 向左
                parent =node;
                node = node.left;
            }
        }

        if(node == null){
            // 未找到
            return null;
        }

        // 没有节点,直接删除
        if(node.left == null && node.right == null){
            if (parent == null){
                // 说明是root
                root = null;
            }else {
                if (parent.left == node){
                    parent.left = null;
                }else {
                    parent.right = null;
                }
            }
            size--;
            return node.data;
        }

        // 左右节点都不为空，要将右子树最小的放到当前位置
        if (node.left != null && node.right!=null){
            // 右树的的最小节点
            Node<T> min = node.right;
            Node<T> minParent = node;
            while (min.left != null){
                min = min.left;
                minParent = min;
            }
            // 交换到当前位置
            T data = node.data;
            node.data =  min.data;

            // 删除该最小节点
            if (minParent.left == min){
                minParent.left = min.right;
            }else {
                minParent.right = min.right;
            }
            min.right = null;
            size--;
            return data;
        }



        // 只有一个节点
        if (parent == null){
            // 说明是root
            if (node.left != null){
                root = node.left;
                node.left = null;
            }else {
                root = node.right;
                node.right = null;
            }
        }else {
            if (parent.left == node){
                if (node.left != null){
                    parent.left = node.left;
                    node.left = null;
                }else {
                    parent.left = node.right;
                    node.right = null;
                }
            }else {
                if (node.left!=null){
                    parent.right = node.left;
                    node.left = null;
                }else {
                    parent.right = node.right;
                    node.right = null;
                }
            }
        }
        size--;

        return node.data;
    }

    protected Node<T> findNode(T data){
        if(isEmpty()){
            return null;
        }
        Node<T> node = root;
        while (node!=null){
            if (data.compareTo(node.data) == 0){
                return node;
            }else if (data.compareTo(node.data) < 0){
                node = node.left;
            }else {
                node = node.right;
            }
        }
        return null;
    }


    private Node<T> search(Node<T> node, T data){
        if(node == null){
            return null;
        }
        if(node.data.compareTo(data) == 0){
            return node;
        }else if(node.data.compareTo(data) > 0){
            // 左子树查找
            return search(node.left,data);
        }else{
            // 右子树查找
            return search(node.right,data);
        }
    }

    private Node<T> newNode(T data){
        Node<T> node = new Node<>();
        node.data = data;
        node.left = null;
        node.right = null;
        return node;
    }

    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    @Override
    public String toString() {
        if(root == null){
            return "[]";
        }
        // 中序遍历
        String str = toString(root);
        return "["+str+"]";
    }

    private String toString(Node<T> node){
        if (node == null){
            return "";
        }
        StringBuilder builder = new StringBuilder();
        String leftStr = toString(node.left);
        if (!leftStr.isEmpty()){
            builder.append(leftStr).append(",");
        }
        String nodeStr = node.data.toString();
        builder.append(nodeStr);
        String rightStr = toString(node.right);
        if (!rightStr.isEmpty()){
            builder.append(",").append(rightStr);
        }
        return builder.toString();
    }

}
